/*
 * IdealGenerator.java
 *
 * Created on February 11, 2004, 11:49 AM
 */

package com.milowski.monos.monomial;

// TODO: fix this import
//import com.milowski.monos.language.functions.Write;
import java.util.*;
import java.util.logging.*;
import java.io.*;

/**
 * A collection of algorithms that can be run on
 * monomial ideal generating sets.
 * @author  R. Alexander Milowski
 */
public class IdealGenerator {
   
   static Logger log = Logger.getLogger("com.milowski.monos.monomial");
   static int defaultTrackNumber = 1;
   static boolean defaultFrontOrder = true;
   static {
      String value = System.getProperty("com.milowski.monos.monomial.IdealGenerator.tracks");
      if (value!=null) {
         defaultTrackNumber = Integer.parseInt(value);
      }
      value = System.getProperty("com.milowski.monos.monomial.IdealGenerator.frontOrder");
      if (value!=null) {
         defaultFrontOrder = value.equals("true");
      }
   }
   
   /**
    * An adjustment to a monomial.
    * @author R. Alexander Milowski
    */
   static public class Adjustment {
      public short from;
      public short to;
      Adjustment(short from,short to) {
         this.from = from;
         this.to = to;
      }
   }
   
   /** Creates a new instance of IdealGenerator */
   private IdealGenerator() {
   }
   
   /*
    * Finds the least common multiple (LCM) of a set of monomials.
    * @param monomialList The set of monomials to consider.
    * @return The LCM as a monomial.
    */
   public static Monomial lcm(List monomialList) {
      short [] result = new short[((Monomial)monomialList.get(0)).getValues().length];

      Iterator monomials = monomialList.iterator();
      
      for (int i=0; i<result.length; i++) {
         result[i] = 0;
      }
      while (monomials.hasNext()) {
         Monomial monomial = (Monomial)monomials.next();
         short [] comparison = monomial.getValues();
         for (int i=0; i<result.length; i++) {
            if (comparison[i]>result[i]) {
               result[i] = comparison[i];
            }
         }
      }
      return new Monomial(result);
   }

   /**
    * Intersects two monomial ideals represented by their minimal generators.  This method allows
    * the monomial tree to be reused--which may help memory consume and/or garbage collection to
    * stabalize.
    * @param mtree The monomial tree to use for the intersect.
    * @param first The first monomial ideal's minimal generators.
    * @param second The second monomial ideal's minimal generators.
    * @return The resulting ideal represented by a list of minimal generators.
    */
   public static MonomialIdeal intersect(MonomialTree mtree,MonomialIdeal first,MonomialIdeal second) {
      mtree.reset();
      mtree.combine(true,true,true,first,second);
      return mtree.getIdealGenerator();
   }

   /**
    * Intersects two monomial ideals represented by their minimal generators.
    * @param first The first monomial ideal's minimal generators.
    * @param second The second monomial ideal's minimal generators.
    * @return The resulting ideal represented by a list of minimal generators.
    */
   public static MonomialIdeal intersect(MonomialIdeal first,MonomialIdeal second) {
      // TODO: check for same lex order?
      MonomialTree mtree = new MonomialTree(first.getLexOrder());
      mtree.combine(true,true,true,first,second);
      return mtree.getIdealGenerator();
   }

   /**
    * Intersects two monomial ideal lists using the lex order specified.
    * @param order The lex order to use.
    * @param first The first monomial list to intersect.
    * @param second The second monomial list to intersect.
    * @return The resulting ideal represented by a list of minimal generators.
    */
   public static MonomialIdeal intersect(LexOrder order,List first,List second) {
      // TODO: check for same lex order?
      MonomialTree mtree = new MonomialTree(order);
      mtree.combine(true,true,true,first,second);
      return mtree.getIdealGenerator();
   }

   /**
    * Returns the Alexander Dual components given a monomial ideal as a minimal
    * generating set.
    * @param gen The minimal generators of the ideal.
    * @return A list of primary ideal components.
    */
   public static List dualComponents(MonomialIdeal gen) {
      Monomial lcm = lcm(gen);
      return dualComponents(lcm,gen);
   }
   
   /**
    * Returns the Alexander Dual components given a monomial ideal as a minimal
    * generating set.
    * @param lcm The LCM of the minimal generators.
    * @param gen The minimal generators of the ideal.
    * @return A list of primary ideal components.
    */
   public static List dualComponents(Monomial lcm,MonomialIdeal gen) {
      short [] lcmValues = lcm.getValues();
      int width = lcmValues.length;
      short [] tempMonomial = new short[width];
      
      
      List intersection = new ArrayList();
      
      LexOrder order = gen.getLexOrder();
      Iterator monomials = gen.iterator();
      while (monomials.hasNext()) {
       
         Monomial monomial = (Monomial)monomials.next();
         short [] mvalues = monomial.getValues();
         
         for (int j=0; j<width; j++) {
            // Calculate the variable's exponent
            tempMonomial[j] = mvalues[j]==0 ? (short)0 : (short)(lcmValues[j]+1-mvalues[j]);
         }
         
         MonomialIdeal intersectionGenerator = new MonomialIdeal(order);
         for (int j=0; j<width;  j++) {
            if (tempMonomial[j]!=0) {
               intersectionGenerator.add(new Monomial(j,tempMonomial));
            }
         }
         intersection.add(intersectionGenerator);
      }
      return intersection;
   }
 
   /**
    * Calculates the Alexander Dual and returns it as a set of minimal generators.
    * @param frontOrder A true value specifices that the result of intersecting each
    *                   pair of components of the dual will be pre-appended to the remaining
    *                   pairs.
    * @param gen The minimal generating set to use.
    * @return The dual represented by minimal generators.
    */
   public static MonomialIdeal dual(boolean frontOrder,MonomialIdeal gen) {
      Monomial lcm = lcm(gen);
      return dual(lcm,frontOrder,1,gen);
   }
   
   /**
    * Calculates the Alexander Dual and returns it as a set of minimal generators.
    * @param lcm The LCM of the minimal generators.
    * @param frontOrder A true value specifices that the result of intersecting each
    *                   pair of components of the dual will be pre-appended to the remaining
    *                   pairs.
    * @param gen The minimal generating set to use.
    * @return The dual represented by minimal generators.
    */
   public static MonomialIdeal dual(Monomial lcm,boolean frontOrder,MonomialIdeal gen) {
      return dual(lcm,frontOrder,1,gen);
   }
   
   /**
    * Calculates the Alexander Dual and returns it as a set of minimal generators.  This method divides the
    * list into a number of tracks and fully intersects those tracks first.
    * @param lcm The LCM of the minimal generators.
    * @param frontOrder A true value specifices that the result of intersecting each
    *                   pair of components of the dual will be pre-appended to the remaining
    *                   pairs.
    * @param numberOfTracks The number of tracks to use.
    * @param gen The minimal generating set to use.
    * @return The dual represented by minimal generators.
    */
   public static MonomialIdeal dual(Monomial lcm,boolean frontOrder,int numberOfTracks,MonomialIdeal gen) {
      
      log.fine("Calculating dual's decomposition:");
      
      List components = dualComponents(lcm,gen);

      if (log.isLoggable(Level.FINE)) {
         log.fine("  dual components calcuated, intersecting...");
         log.fine("     pairs: "+(components.size()-1));
      }

      long start = System.currentTimeMillis();
      int trackSize = components.size()/numberOfTracks;
      if (trackSize==0) {
         numberOfTracks = 1;
      }
      if (numberOfTracks==1 || trackSize==1) {
         int pair = 0;
         MonomialTree mtree = new MonomialTree(((LexOrderedList)components.get(0)).getLexOrder());
         while (components.size()!=1) {
            MonomialIdeal first = (MonomialIdeal)components.get(0);
            MonomialIdeal second = (MonomialIdeal)components.get(1);
            pair++;

            long istart = System.currentTimeMillis();
            if (log.isLoggable(Level.FINER)) {
               StringWriter w = new StringWriter();
               w.write(first.toString());
               w.write(" and ");
               w.write(second.toString());
               log.fine("  pair "+pair+" is "+w.toString());
            }
            //LexOrderedList result = intersect(mtree,first,second);
            if (log.isLoggable(Level.FINE)) {
               log.fine("  working on "+pair+" ("+first.size()+","+second.size()+")...");
            }
            MonomialIdeal result = intersect(first,second);
            if (log.isLoggable(Level.FINE)) {
               log.fine("  pair "+pair+" ("+first.size()+","+second.size()+") = "+result.size()+", time = "+(System.currentTimeMillis()-istart)+", remaining = "+(components.size()-1));
            }

            if (frontOrder) {
               components.remove(0);
               components.set(0,result);
            } else {
               components.remove(0);
               components.remove(0);
               components.add(result);
            }
            if (log.isLoggable(Level.FINER)) {
               log.fine("  pair "+pair+" result is "+result.toString());
            }
         }
         if (log.isLoggable(Level.FINE)) {
            log.fine("  dual complete, elapsed = "+(System.currentTimeMillis()-start));
         }

         return (MonomialIdeal)components.get(0);
      } else {
         // TODO: there is a problem here when the input size is 1
         if (log.isLoggable(Level.FINE)) {
            log.fine("  track size = "+trackSize);
         }
         int trackNumber = 0;
         int startIndex = 0;
         int endIndex = trackSize;
         List trackResults = new ArrayList();
         LexOrder order = ((LexOrderedList)components.get(0)).getLexOrder();
         MonomialTree mtree = new MonomialTree(order);
         while (startIndex<components.size()) {
            List track = new ArrayList(components.subList(startIndex,endIndex));
            
            trackNumber++;
            int pair = 0;
            while (track.size()>1) {
               MonomialIdeal first = (MonomialIdeal)track.get(0);
               MonomialIdeal second = (MonomialIdeal)track.get(1);
               pair++;

               long istart = System.currentTimeMillis();
               int firstSize = first.size();
               int secondSize = second.size();
               boolean output = false;
               if (log.isLoggable(Level.FINE) && firstSize*secondSize>200000) {
                  output = true;
                  log.fine("  track "+trackNumber+" computing pair "+pair+" ("+first.size()+","+second.size()+")...");
               }
               //LexOrderedList result = intersect(mtree,first,second);
               MonomialIdeal result = intersect(first,second);
               if (log.isLoggable(Level.FINE)) {
                  if (output) {
                     log.fine("     result ->"+result.size()+", time = "+(System.currentTimeMillis()-istart)+", remaining = "+(track.size()-1));
                  } else {
                     log.fine("  track "+trackNumber+" computed pair "+pair+" ("+first.size()+","+second.size()+")="+result.size()+", time = "+(System.currentTimeMillis()-istart)+", remaining = "+(track.size()-1));
                  }
               }

               if (frontOrder) {
                  track.remove(0);
                  track.set(0,result);
               } else {
                  track.remove(0);
                  track.remove(0);
                  track.add(result);
               }
            }
            trackResults.add(track.get(0));
            startIndex = endIndex;
            endIndex += trackSize;
            if (endIndex>components.size()) {
               endIndex = components.size();
            }
         }
         int pair = 0;
         while (trackResults.size()!=1) {
            MonomialIdeal first = (MonomialIdeal)trackResults.get(0);
            MonomialIdeal second = (MonomialIdeal)trackResults.get(1);
            pair++;

            long istart = System.currentTimeMillis();
            //LexOrderedList result = intersect(mtree,first,second);
            LexOrderedList result = intersect(first,second);
            if (log.isLoggable(Level.FINE)) {
               log.fine("  final pair "+pair+" ("+first.size()+","+second.size()+") time = "+(System.currentTimeMillis()-istart)+", remaining = "+(trackResults.size()-1));
            }

            trackResults.remove(0);
            trackResults.set(0,result);
         }
         if (log.isLoggable(Level.FINE)) {
            log.fine("  dual complete, elapsed = "+(System.currentTimeMillis()-start));
         }

         return (MonomialIdeal)trackResults.get(0);
      }
   }

   /**
    * Decomposes an ideal into its irredundant irreducible decomposition using the
    * Alexander Dual.
    * @param frontOrder A true value specifices that the result of intersecting each
    *                   pair of components of the dual will be pre-appended to the remaining
    *                   pairs.
    * @param gen The minimal generating set to use.
    * @return The decomposition represent as a list of primary components.
    */
   public static LexOrderedList decompose(boolean frontOrder,MonomialIdeal gen) {
      
      log.fine("Calculating lcm...");
      Monomial lcm = lcm(gen);
      short [] lcmValues = lcm.getValues();
      int width = lcmValues.length;
      short [] tempMonomial = new short[width];
      
      log.fine("Calculating dual...");
      MonomialIdeal dual = dual(lcm,frontOrder,defaultTrackNumber,gen);
      LexOrder order = gen.getLexOrder();
      LexOrderedList components = new LexOrderedList(order);

      log.fine("Calculating components of intersection...");
      Iterator dualGens = dual.iterator();
      while (dualGens.hasNext()) {
         Monomial monomial = (Monomial)dualGens.next();
         short [] mvalues = monomial.getValues();
         
         for (int j=0; j<width; j++) {
            // Calculate the variable's exponent
            tempMonomial[j] = mvalues[j]==0 ? (short)0 : (short)(lcmValues[j]+1-mvalues[j]);
         }
         
         MonomialIdeal intersectionGenerator = new MonomialIdeal(order);
         for (int j=0; j<width;  j++) {
            if (tempMonomial[j]!=0) {
               intersectionGenerator.add(new Monomial(j,tempMonomial));
            }
         }
         components.add(intersectionGenerator);
         
      }
      return components;
   }

   /**
    * Adjusts a monomial ideal to make it generic.  This modifies the original
    * ideal passed as a parameter.
    * @param gen The minimal generating set of the ideal.
    * @return A list of adjustments made.
    */
   public static Adjustment [][] makeGeneric(LexOrderedList gen) {
      
      Monomial first = (Monomial)gen.get(0);
      int width = first.getValues().length;
      //int [] lexOrder = new int[width];
      Adjustment[][] adjustments = new Adjustment[width][];
      // Adjust the monomials for each variable
      for (short var=0; var<width; var++) {
         if (log.isLoggable(Level.FINER)) {
            log.finer("Var "+var);
         }

         /*
         for (int i=0,j=var; i<width; i++) {
            lexOrder[i] = j;
            j++;
            if (j>=width) {
               j = 0;
            }
         }*/
         //Group the monomial list 
         Map monomialsByPower = new HashMap();
         Iterator monomials = gen.iterator();
         while (monomials.hasNext()) {
            Monomial m = (Monomial)monomials.next();
            short [] mvalues = m.getValues();
            if (mvalues[var]>0) {
               Short e = new Short(mvalues[var]);
               List l = (List)monomialsByPower.get(e);
               if (l==null) {
                  l = new ArrayList();
                  if (log.isLoggable(Level.FINEST)) {
                     log.finest("Appending "+m+" for "+e);
                  }
                  l.add(m);
                  monomialsByPower.put(e,l);
               } else {
                  // This must be added in lex order
                  int len = l.size();
                  boolean done = false;
                  for (int i=0; !done && i<len; i++) {
                     Monomial o = (Monomial)l.get(i);
                     if (o.before(m)) {
                        if (log.isLoggable(Level.FINEST)) {
                           log.finest("Inserting "+m+" before "+o+" for "+e);
                        }
                        l.add(i,m);
                        done = true;
                     }
                  }
                  if (!done) {
                     if (log.isLoggable(Level.FINEST)) {
                        log.finest("Appending "+m+" for "+e);
                     }
                     l.add(m);
                  }
                  /*
                  if (log.isLoggable(Level.FINEST)) {
                     log.finest("Appending "+m+" for "+e);
                  }
                  l.add(m);
                   */
               }
            }
         }
         
         // Sort the powers so we proceed least to greatest
         ArrayList klist = new ArrayList();
         klist.addAll(monomialsByPower.keySet());
         Collections.sort(klist);
         
         Iterator powers = klist.iterator();
         
         // Figure out how many will be adjusted
         int conflictCount = 0;
         boolean counting = false;
         while (powers.hasNext()) {
            Short e = (Short)powers.next();
            List toAdjust = (List)monomialsByPower.get(e);
            if (toAdjust.size()==1) {
               if (counting) {
                  conflictCount += 1;
               }
            } else {
               counting = true;
               conflictCount += toAdjust.size();
            }
         }
         // Allocate the adjustments
         Adjustment [] adjusted = new Adjustment[conflictCount];
         
         // Iterate all the powers and adjust them to unique values.
         powers = klist.iterator();
         int currentAdjustment = 0;
         short adjustment = 0;
         short lastPower = 0;
         while (powers.hasNext()) {
            Short e = (Short)powers.next();
            List toAdjust = (List)monomialsByPower.get(e);
            if (log.isLoggable(Level.FINEST)) {
               log.finest("lastPower="+lastPower);
            }
            if (e.shortValue()>lastPower) {
               adjustment = 0;
            } else if (e.shortValue()==lastPower) {
               adjustment = 1;
            }
            if (toAdjust.size()>1) {
               if (log.isLoggable(Level.FINER)) {
                  log.finer("Adjusting var "+var+" for conflict power "+e+":");
               }
               Iterator listMonomials = toAdjust.iterator();
               int count = 0;
               while (listMonomials.hasNext()) {
                  Monomial m = (Monomial)listMonomials.next();
                  lastPower = (short)(m.getValues()[var] + adjustment);
                  adjusted[currentAdjustment++] = new Adjustment(e.shortValue(),lastPower);
                  if (log.isLoggable(Level.FINER)) {
                     log.finer("   "+m+" adjust "+e+" -> "+lastPower);
                  }
                  m.getValues()[var] = lastPower;
                  if (listMonomials.hasNext()) {
                     adjustment++;
                  }
                  count++;
               }
            } else if (adjustment!=0) {
               if (log.isLoggable(Level.FINER)) {
                  log.finer("Adjusting var "+var+" for non-conflict power "+e+":");
               }
               Monomial m = (Monomial)toAdjust.get(0);
               lastPower = (short)(m.getValues()[var] + adjustment);
               adjusted[currentAdjustment++] = new Adjustment(e.shortValue(),lastPower);
               if (log.isLoggable(Level.FINER)) {
                  log.finer("   "+m+" adjust "+e+" -> "+lastPower);
               }
               m.getValues()[var] = lastPower;
            } else {
               if (log.isLoggable(Level.FINER)) {
                  log.finer("Adjustment at zero for "+e);
               }
            }
         }
         adjustments[var] = adjusted;
      }
      return adjustments;
   }
   
   /**
    * Makes an ideal artinian.  This modifies the ideal passed as a
    * parameter.
    * @param gen The minimal generating set of the ideal.
    * @return The list of exponent powers added--one for each variable.
    */
   public static short [] makeArtinian(LexOrderedList gen) {
      Monomial first = (Monomial)gen.get(0);
      int width = first.getValues().length;
      boolean [] alreadyThere = new boolean[width];
      short [] maximal = new short[width];
      for (short var =0; var<width; var++) {
         short max = 0;
         Iterator monomials = gen.iterator();
         while (monomials.hasNext()) {
            Monomial m = (Monomial)monomials.next();
            short [] mvalues = m.getValues();
            if (mvalues[var]>max) {
               max = mvalues[var];
               boolean single = true;
               for (short i=0; i<width; i++) {
                  if (i!=var && mvalues[i]!=0) {
                     single = false;
                  }
               }
               if (single) {
                  alreadyThere[var] = true;
               }
            }
         }
         max++;
         maximal[var] = max;
      }
      short [] mvalues = new short[width];
      for (short var = 0; var<width; var++) {
         if (alreadyThere[var]) {
            maximal[var] = 0;
         } else {
            for (short i=0; i<width; i++) {
               mvalues[i] = i==var ? maximal[i] : 0;
            }
            gen.add(new Monomial(mvalues));
         }
      }
      return maximal;
   }
   
   /**
    * Finds a starting facet of a scarf complex.  The ideal must be
    * generic and artinian.
    * @param gen The minimal generating set.
    * @return The LCM of the facet.
    */
   public static Monomial findFacet(LexOrderedList gen) {
      if (gen.size()==0) {
         return null;
      }
      
      if (log.isLoggable(Level.FINER)) {
         log.finer("Finding largest facet:");
      }
      // Brute-force algorithm 
      short [] facet = new short[((Monomial)gen.get(0)).getValues().length];
      Iterator monomials = gen.iterator();
      while (monomials.hasNext()) {
         Monomial toCheck = (Monomial)monomials.next();
         if (facet[0]<toCheck.getValues()[0]) {
            facet[0] = toCheck.getValues()[0];
         }
      }
      if (log.isLoggable(Level.FINER)) {
         log.finer("Var 0: "+facet[0]);
      }
      LexOrder order = gen.getLexOrder();
      
      MonomialTree lastTree = null;
      for (int varIndex = 1; varIndex<facet.length; varIndex++) {
         order = order.project();
         //System.out.println("Variable "+varIndex);
         MonomialTree mtree = new MonomialTree(order);
         //mtree.setVerbose(true);
         //short [] mvalues = new short[facet.length-varIndex]; 
         monomials = lastTree==null ? gen.iterator() : lastTree.iterator(true);
         while (monomials.hasNext()) {
            Monomial toCheck = (Monomial)monomials.next();
            if (log.isLoggable(Level.FINER)) {
               log.finer("Adding "+toCheck);
            }
            mtree.add(toCheck,varIndex);
            //mtree.add(toCheck,1);
            //System.arraycopy(toCheck.getValues(), varIndex, mvalues, 0, mvalue,s.length);
            //Monomial tempMonomial = new Monomial(mvalues);
            //System.out.println("Converting: "+toCheck);
            //System.out.println("            "+tempMonomial);
            //mtree.add(tempMonomial);
         }
         mtree.minimize();
         MonomialTree.Entry top = mtree.getRoot().getFirstChild();
         while (top.getRightSibling()!=null) {
            top = top.getRightSibling();
         }
         facet[varIndex] = top.getValue();
         if (log.isLoggable(Level.FINER)) {
            log.finer("Var "+varIndex+": "+facet[varIndex]);
         }
         lastTree = mtree;
      }
      
      return new Monomial(facet);
   }
   
   /**
    * Computes the irredundant irreducible decomposition of a monomial ideal
    * using the Scarf Complex.
    * @param gen The minimal generators of the ideal.
    * @return The decomposition represented as a list of primary components.
    */
   public static LexOrderedList scarfMethodDecompose(LexOrderedList gen) {
      if (log.isLoggable(Level.FINE)) {
         log.fine("Making generic.");
      }
      IdealGenerator.Adjustment [][] adjustments = IdealGenerator.makeGeneric(gen);
      if (log.isLoggable(Level.FINE)) {
         log.fine("Making artinian.");
      }
      short [] maximal = IdealGenerator.makeArtinian(gen);
      ScarfComplex splex = new ScarfComplex(gen);
      if (log.isLoggable(Level.FINE)) {
         log.fine("Finding facet.");
      }
      Monomial largestFacet = IdealGenerator.findFacet(gen);
      if (log.isLoggable(Level.FINE)) {
         log.fine("Calculating decomposition.");
      }
      MonomialTree output = splex.getDecomposition(largestFacet);
      output.adjust(adjustments);
      if (log.isLoggable(Level.FINEST)) {
         log.finest("Dumping monomial tree before removing divisors.");
         log.finest(output.toString());
      }
      output.removeDivisors();
      
      if (log.isLoggable(Level.FINE)) {
         log.fine("Loading decomposition.");
      }
      Iterator facets = output.iterator();
      LexOrderedList components = new LexOrderedList(gen.getLexOrder());
      short [] mvalues = new short[((Monomial)gen.get(0)).getValues().length];
      while (facets.hasNext()) {
         MonomialTree.Entry [] facet = (MonomialTree.Entry [])facets.next();
         LexOrderedList component = new MonomialIdeal(gen.getLexOrder());
         for (int i=0; i<facet.length; i++) {
            short current = facet[i].getValue();
            if (current!=0 && current!=maximal[i]) {
            //if (current!=0) {
               for (int j=0; j<mvalues.length; j++) {
                  mvalues[j] = j==i ? facet[i].getValue() : 0;
               }
               component.add(new Monomial(mvalues));
            }
         }
         components.add(component);
      }
      return components;
      
   }
   
   
   
}
